C语言 单链表的反转 |
您所在的位置：网站首页 › 链表 反转 › C语言 单链表的反转 |
C语言 单链表的反转
|
C语言 单链表的反转
一、简述 记--简单的将单链表的数据顺序进行反转。如将原来的顺序1 2 3 4 5 6 7 反转为：7 6 5 4 3 2 1 二、方式1：头插法 2.1 头插法1--类似新建链表 2.1.1 思路：断开链表头，然后以头插法的方式将原链表的数据添加链表。 2.1.2 测试代码 #include #include //链表节点定义 typedef struct s_node { int data; struct s_node* pNext; }Node; Node* create_list_head(); Node* create_new_node(int node_data); int add_node_head(Node* head, Node* new_node); void display_list(Node* head); void free_list(Node* head); Node* revert_list(Node* head); int main(int argc, char *argv[]) { //创建链表 Node* head = create_list_head(); if(NULL == head) { printf("create_list_head failed!\n"); return -1; } //填充数据（添加节点） int i; for(i=1; idata= -1; head->pNext= NULL; } return head; } //创建新节点 Node* create_new_node(int node_data) { Node* new_node = (Node*)malloc(sizeof(Node)); if(NULL != new_node) { new_node->data= node_data; new_node->pNext= NULL; } return new_node; } //头插法 int add_node_head(Node* head, Node* new_node) { if(NULL == head || NULL == new_node) return -1; new_node->pNext = head->pNext; head->pNext = new_node; return 0; } //打印链表数据 void display_list(Node* head) { if(NULL == head) return; Node* tmp = head; printf("list data:"); while(NULL !=(tmp=tmp->pNext)) { printf("%d ", tmp->data); } printf("\n"); } //释放链表 void free_list(Node* head) { if(NULL == head) return; Node* p = head; while(p = p->pNext) { head->pNext = p->pNext; //printf("free:%d\n", p->data); free(p); p = head; } free(head); } //头插方式1-反转链表 Node* revert_list(Node* head) { if(NULL == head) return; Node* p = head->pNext; head->pNext= NULL; Node* tmp = NULL; while(p) { tmp = p->pNext; add_node_head(head, p); p = tmp; } return head; }2.1.3 测试结果 2.2 头插法2 --与方式1雷同 2.2.1 思路：除了第一个逐个往插入到最前面
2.2.2 测试代码 #include #include //链表节点定义 typedef struct s_node { int data; struct s_node* pNext; }Node; Node* create_list_head(); Node* create_new_node(int node_data); int add_node_head(Node* head, Node* new_node); void display_list(Node* head); void free_list(Node* head); Node* revert_list(Node* head); int main(int argc, char *argv[]) { //创建链表 Node* head = create_list_head(); if(NULL == head) { printf("create_list_head failed!\n"); return -1; } //填充数据（添加节点） int i; for(i=1; idata= -1; head->pNext= NULL; } return head; } //创建新节点 Node* create_new_node(int node_data) { Node* new_node = (Node*)malloc(sizeof(Node)); if(NULL != new_node) { new_node->data= node_data; new_node->pNext= NULL; } return new_node; } //头插法 int add_node_head(Node* head, Node* new_node) { if(NULL == head || NULL == new_node) return -1; new_node->pNext = head->pNext; head->pNext = new_node; return 0; } //打印链表数据 void display_list(Node* head) { if(NULL == head) return; Node* tmp = head; printf("list data:"); while(NULL !=(tmp=tmp->pNext)) { printf("%d ", tmp->data); } printf("\n"); } //释放链表 void free_list(Node* head) { if(NULL == head) return; Node* p = head; while(p = p->pNext) { head->pNext = p->pNext; //printf("free:%d\n", p->data); free(p); p = head; } free(head); } //新建链表方式-反转链表 Node* revert_list(Node* head) { if(NULL == head) return; Node* p = head->pNext; Node* q = NULL; while(q = p->pNext) { p->pNext = q->pNext;//分离q add_node_head(head, q);//将q插入到首元素位置 } return head; }2.2.3 测试结果 三、方式2 尾插方式 3.1 思路：找到最后一个元素，然后从第一个元素逐个插入到尾部。
3.2 测试代码 #include #include //链表节点定义 typedef struct s_node { int data; struct s_node* pNext; }Node; Node* create_list_head(); Node* create_new_node(int node_data); int add_node_tail(Node* head, Node* new_node); void display_list(Node* head); void free_list(Node* head); Node* revert_list(Node* head); int main(int argc, char *argv[]) { //创建链表 Node* head = create_list_head(); if(NULL == head) { printf("create_list_head failed!\n"); return -1; } //填充数据（添加节点） int i; for(i=1; idata= -1; head->pNext= NULL; } return head; } //创建新节点 Node* create_new_node(int node_data) { Node* new_node = (Node*)malloc(sizeof(Node)); if(NULL != new_node) { new_node->data= node_data; new_node->pNext= NULL; } return new_node; } //尾插法 int add_node_tail(Node* tail, Node* new_node) { if(NULL == tail || NULL == new_node) return -1; new_node->pNext = tail->pNext; //新节点指向原来的tail->pNext tail->pNext = new_node;//新节点成为tail->pNext return 0; } //打印链表数据 void display_list(Node* head) { if(NULL == head) return; Node* tmp = head; printf("list data:"); while(NULL !=(tmp=tmp->pNext)) { printf("%d ", tmp->data); } printf("\n"); } //释放链表 void free_list(Node* head) { if(NULL == head) return; Node* p = head; while(p = p->pNext) { head->pNext = p->pNext; //printf("free:%d\n", p->data); free(p); p = head; } free(head); } //尾插方式-反转链表 Node* revert_list(Node* head) { if(NULL == head) return; Node *p = head->pNext, *end = head; while( NULL != end->pNext )//使得end指向链表最后一个元素 { end = end->pNext; } while(p != end) { head->pNext = p->pNext;//分离p add_node_tail(end, p);//将p插入到末尾位置 p = head->pNext;//p指向第一个元素 } return head; }3.3 测试结果
四、方法3 递归反转 1、递归结束边界：节点为NULL, 或当前节点指向NULL 2、状态转移方程：反转(1到N) = 先反转(1到N-1)，再将N添加到尾部
测试代码：（注意，本例子与上面的例子稍有差异，为了方便表述，头节点也作为使用并存储数据了） #include #include #define NODE_COUNT 3 //链表节点定义 typedef struct s_node { int data; struct s_node* pNext; }Node; Node* create_list_head(); Node* create_new_node(int node_data); int add_node_tail(Node* head, Node* new_node); void display_list(Node* head); void free_list(Node* head); Node* revert_list(Node* head); int main(int argc, char *argv[]) { //创建链表 Node* head = create_list_head(); if(NULL == head) { printf("create_list_head failed!\n"); return -1; } //填充数据（添加节点） int i; for(i=1; i < NODE_COUNT; i++) add_node_tail(head, create_new_node(i)); //打印原来链表数据 printf("befor "); display_list(head); //反转链表 head = revert_list(head); printf("after "); display_list(head); //释放链表空间 free_list(head); getchar(); return 0; } //创建新节点 Node* create_new_node(int node_data) { Node* new_node = (Node*)malloc(sizeof(Node)); if(NULL != new_node) { new_node->data= node_data; new_node->pNext= NULL; } return new_node; } //创建链表 Node* create_list_head() { return create_new_node(NODE_COUNT); } //尾插法 int add_node_tail(Node* tail, Node* new_node) { if(NULL == tail || NULL == new_node) return -1; new_node->pNext = tail->pNext; //新节点指向原来的tail->pNext tail->pNext = new_node;//新节点成为tail->pNext return 0; } //打印链表数据 void display_list(Node* head) { if(NULL == head) return; Node* tmp = head; printf("list data:"); while(NULL != tmp) { printf("%d ", tmp->data); tmp = tmp->pNext; } printf("\n"); } //释放链表 void free_list(Node* head) { if(NULL == head) return; Node* p = head; while (p) { head = head->pNext; printf("free:%d\n", p->data); free(p); p = head; } } //反转链表 Node* revert_list(Node* head) { if (NULL == head || NULL == head->pNext) { return head; } Node* new_head = revert_list(head->pNext); head->pNext->pNext = head; head->pNext = NULL; return new_head; }测试结果：
|
【本文地址】
今日新闻 |
推荐新闻 |